﻿// 3703. 括号的匹配.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <stack>


using namespace std;
/*
https://www.acwing.com/problem/content/3706/


在算术表达式中，除了加、减、乘、除等运算外，往往还有括号。

包括有大括号 {}，中括号 []，小括号 ()，尖括号 <> 等。

对于每一对括号，必须先左边括号，然后右边括号；如果有多个括号，则每种类型的左括号和右括号的个数必须相等；
对于多重括号的情形，按运算规则，从外到内的括号嵌套顺序为：大括号->中括号->小括号->尖括号，另外相同的括号可以嵌套。

例如，{[()]},{(())},{{}} 为一个合法的表达式，而 ([{}]),{([])},[{<>}] 都是非法的。

输入格式
第一行包含整数 n，表示共有 n个表达式需要判断。

接下来 n行，每行包含一个括号表达式。

输出格式
每行输出一个表达式的判断结果。

如果合法输出 YES，否则输出 NO。

数据范围
1≤n≤100

表达式长度不超过 100。

输入样例：
5
{[(<>)]}
[()]
<>()[]{}
[{}]
{()}
输出样例：
YES
YES
YES
NO
YES
*/


string str;

const int NONE = 0;
const int LARGE = 1;
const int MID = 2;
const int SMA = 3;
const int ANG = 4;

int currState;

//not AC
int main()
{
	int n;
	cin >> n;
	while(n--){
		cin >> str;
		stack<char> st;
		currState = NONE;
		int sucfalg = 1;
		for (int i = 0; i < str.size(); i++) {
			char c = str[i];
			if (c == '{' && currState <= LARGE) { st.push(c); currState = LARGE; }
			else if (c == '[' && currState <= MID) { st.push(c);  currState = MID; }
			else if (c == '(' && currState <= SMA) { st.push(c);  currState = SMA; }
			else if (c == '<' && currState <= ANG) { st.push(c);  currState = ANG; }
			else if (c == '}' && !st.empty() && st.top() == '{') {
				st.pop();
				if (st.empty()) { currState = NONE; }
				else { currState = LARGE; }
			}
			else if (c == ']' && !st.empty() && st.top() == '[') {
				st.pop();
				if (st.empty()) { currState = NONE; }
				else { currState = MID; }
			}
			else if (c == ')' && !st.empty() && st.top() == '(') {
				st.pop();
				if (st.empty()) { currState = NONE; }
				else { currState = SMA; }
			}
			else if (c == '>' && !st.empty() && st.top() == '<') {
				st.pop();
				if (st.empty()) { currState = NONE; }
				else { currState = ANG; }
			}
			else {
				sucfalg = 0;  break;
			}
		}

		if (st.empty() && sucfalg== 1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}

	return 0;
}

 